/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

/*
 *    BIFParser.java
 *    Copyright (C) 2003 University of Waikato, Hamilton, New Zealand
 *
 */
package weka.gui.graphvisualizer;

import java.io.InputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.StringReader;
import java.util.StringTokenizer;

import weka.core.FastVector;

import org.w3c.dom.Document;
import org.w3c.dom.NodeList;
import org.w3c.dom.Element;

/**
 * This class parses an inputstream or a string in XMLBIF ver. 0.3 format, and
 * builds the datastructures that are passed to it through the constructor.
 * 
 * @author Ashraf M. Kibriya (amk14@cs.waikato.ac.nz)
 * @version $Revision: 7059 $ - 24 Apr 2003 - Initial version (Ashraf M.
 *          Kibriya)
 */
public class BIFParser implements GraphConstants {

	/** These holds the nodes and edges of the graph */
	protected FastVector m_nodes, m_edges;
	/**
	 * This holds the name of the graph (i.e. the name of network tag in XMLBIF
	 * input)
	 */
	protected String graphName;
	/** This holds the string to be parsed */
	protected String inString;
	/** This holds the InputStream to be parsed */
	protected InputStream inStream;

	/**
	 * Constructor (if our input is a String)
	 * 
	 * @param input
	 *            the string to be parsed (should not be null)
	 * @param nodes
	 *            vector containing GraphNode objects (should be empty)
	 * @param edges
	 *            vector containing GraphEdge objects (should be empty)
	 */
	public BIFParser(String input, FastVector nodes, FastVector edges) {
		m_nodes = nodes;
		m_edges = edges;
		inString = input;
	}

	/**
	 * Constructor (if our input is an InputStream)
	 * 
	 * @param instream
	 *            the InputStream to be parsed (should not be null)
	 * @param nodes
	 *            vector containing GraphNode objects (should be empty)
	 * @param edges
	 *            vector containing GraphEdge objects (should be empty)
	 */
	public BIFParser(InputStream instream, FastVector nodes, FastVector edges) {
		m_nodes = nodes;
		m_edges = edges;
		inStream = instream;
	}

	/**
	 * This method parses the string or the InputStream that we passed in
	 * through the constructor and builds up the m_nodes and m_edges vectors
	 * 
	 * @exception Exception
	 *                if both the inString and inStream are null, i.e. no input
	 *                has been provided
	 * @exception BIFFormatException
	 *                if there is format of the input is not correct. The format
	 *                should conform to XMLBIF version 0.3
	 * @exception NumberFormatException
	 *                if there is an invalid char in the probability table of a
	 *                node.
	 * @return returns the name of the graph
	 */
	public String parse() throws Exception {
		Document dc = null;

		javax.xml.parsers.DocumentBuilderFactory dbf = javax.xml.parsers.DocumentBuilderFactory
				.newInstance();
		dbf.setIgnoringElementContentWhitespace(true);
		javax.xml.parsers.DocumentBuilder db = dbf.newDocumentBuilder();

		if (inStream != null)
			dc = db.parse(inStream);
		else if (inString != null)
			dc = db.parse(new org.xml.sax.InputSource(
					new StringReader(inString)));
		else {
			throw new Exception(Messages.getInstance().getString(
					"BIFParser_Parse_Exception_Text"));
		}

		NodeList nl = dc.getElementsByTagName("NETWORK");

		if (nl.getLength() == 0) {
			throw new BIFFormatException(Messages.getInstance().getString(
					"BIFParser_Parse_BIFFormatException_Text_First"));
		}

		// take only the first network node
		NodeList templist = ((Element) nl.item(0)).getElementsByTagName("NAME");
		graphName = templist.item(0).getFirstChild().getNodeValue();
		// System.out.println("The name of the network is "+
		// templist.item(0).getFirstChild().getNodeValue());

		// Get all the variables
		nl = dc.getElementsByTagName("VARIABLE");
		for (int i = 0; i < nl.getLength(); i++) {

			templist = ((Element) nl.item(i)).getElementsByTagName("NAME");
			if (templist.getLength() > 1)
				throw new BIFFormatException(Messages.getInstance().getString(
						"BIFParser_Parse_BIFFormatException_Text_Second")
						+ (i + 1));

			String nodename = ((org.w3c.dom.Node) templist.item(0))
					.getFirstChild().getNodeValue();
			GraphNode n = new GraphNode(nodename, nodename, GraphNode.NORMAL);
			m_nodes.addElement(n);
			// getting nodes position
			templist = ((Element) nl.item(i)).getElementsByTagName("PROPERTY");
			for (int j = 0; j < templist.getLength(); j++) {
				if (((org.w3c.dom.Node) templist.item(j)).getFirstChild()
						.getNodeValue().startsWith("position")) {
					String xy = templist.item(j).getFirstChild().getNodeValue();
					// System.out.println("x: "+
					// xy.substring(xy.indexOf('(')+1, xy.indexOf(','))+
					// " y: "+
					// xy.substring(xy.indexOf(',')+1, xy.indexOf(')'))
					// );
					n.x = Integer.parseInt(xy.substring(xy.indexOf('(') + 1,
							xy.indexOf(',')).trim());
					n.y = Integer.parseInt(xy.substring(xy.indexOf(',') + 1,
							xy.indexOf(')')).trim());
					break;
				}
			}
			// getting all the outcomes of the node
			templist = ((Element) nl.item(i)).getElementsByTagName("OUTCOME");
			n.outcomes = new String[templist.getLength()];
			for (int j = 0; j < templist.getLength(); j++) {
				n.outcomes[j] = templist.item(j).getFirstChild().getNodeValue();
				// System.out.println("Outcome["+j+"]: "+n.outcomes[j]);
			}
		} // end for (for variables)

		// Get all the edges and probability tables by getting all the
		// definitions
		nl = dc.getElementsByTagName("DEFINITION");
		for (int i = 0; i < nl.getLength(); i++) {

			templist = ((Element) nl.item(i)).getElementsByTagName("FOR");
			// the Label of the node the edges are coming into
			String nid = templist.item(0).getFirstChild().getNodeValue();

			// getting the GraphNode object with the above label
			GraphNode n = (GraphNode) m_nodes.elementAt(0);
			for (int j = 1; j < m_nodes.size() && !n.ID.equals(nid); j++)
				n = (GraphNode) m_nodes.elementAt(j);

			templist = ((Element) nl.item(i)).getElementsByTagName("GIVEN");
			int parntOutcomes = 1; // for creating the probability table later
									// on
			// creating all the edges coming into the node
			for (int j = 0; j < templist.getLength(); j++) {
				nid = templist.item(j).getFirstChild().getNodeValue();

				GraphNode n2 = (GraphNode) m_nodes.elementAt(0);
				for (int k = 1; k < m_nodes.size() && !n2.ID.equals(nid); k++)
					n2 = (GraphNode) m_nodes.elementAt(k);
				m_edges.addElement(new GraphEdge(m_nodes.indexOf(n2), m_nodes
						.indexOf(n), 1));

				parntOutcomes *= n2.outcomes.length;
			}

			// creating the probability table for the node
			templist = ((Element) nl.item(i)).getElementsByTagName("TABLE");
			if (templist.getLength() > 1)
				throw new BIFFormatException(Messages.getInstance().getString(
						"BIFParser_Parse_BIFFormatException_Text_Second_Alpha")
						+ n.ID);

			String probs = templist.item(0).getFirstChild().getNodeValue();
			StringTokenizer tk = new StringTokenizer(probs, " \n\t");

			if (parntOutcomes * n.outcomes.length > tk.countTokens())
				throw new BIFFormatException(
						Messages.getInstance()
								.getString(
										"BIFParser_Parse_BIFFormatException_Text_Third")
								+ n.ID
								+ Messages
										.getInstance()
										.getString(
												"BIFParser_Parse_BIFFormatException_Text_Fourth"));
			else if (parntOutcomes * n.outcomes.length < tk.countTokens())
				throw new BIFFormatException(
						Messages.getInstance()
								.getString(
										"BIFParser_Parse_BIFFormatException_Text_Fifth")
								+ n.ID
								+ Messages
										.getInstance()
										.getString(
												"BIFParser_Parse_BIFFormatException_Text_Sixth"));
			else {
				n.probs = new double[parntOutcomes][n.outcomes.length];
				for (int r = 0; r < parntOutcomes; r++)
					// row
					for (int c = 0; c < n.outcomes.length; c++)
						// column
						try {
							n.probs[r][c] = Double.parseDouble(tk.nextToken());
						} catch (NumberFormatException ne) {
							throw ne;
						}
			} // end of creating probability table
		} // endfor (for edges)

		// int tmpMatrix[][] = new int[m_nodes.size()][m_nodes.size()];
		// for(int i=0; i<m_edges.size(); i++)
		// tmpMatrix[((GraphEdge)m_edges.elementAt(i)).src]
		// [((GraphEdge)m_edges.elementAt(i)).dest] =
		// ((GraphEdge)m_edges.elementAt(i)).type;
		// for(int i=0; i<m_nodes.size(); i++) {
		// GraphNode n = (GraphNode)m_nodes.elementAt(i);
		// n.edges = tmpMatrix[i];
		// }

		// Adding parents, and those edges to a node which are coming out from
		// it
		int tmpEdges[], noOfEdgesOfNode[] = new int[m_nodes.size()];
		int noOfPrntsOfNode[] = new int[m_nodes.size()];
		for (int i = 0; i < m_edges.size(); i++) {
			GraphEdge e = (GraphEdge) m_edges.elementAt(i);
			noOfEdgesOfNode[e.src]++;
			noOfPrntsOfNode[e.dest]++;
		}

		for (int i = 0; i < m_edges.size(); i++) {
			GraphEdge e = (GraphEdge) m_edges.elementAt(i);
			GraphNode n = (GraphNode) m_nodes.elementAt(e.src);
			GraphNode n2 = (GraphNode) m_nodes.elementAt(e.dest);
			if (n.edges == null) {
				n.edges = new int[noOfEdgesOfNode[e.src]][2];
				for (int k = 0; k < n.edges.length; k++)
					n.edges[k][0] = -1;
			}
			if (n2.prnts == null) {
				n2.prnts = new int[noOfPrntsOfNode[e.dest]];
				for (int k = 0; k < n2.prnts.length; k++)
					n2.prnts[k] = -1;
			}

			int k = 0;
			while (n.edges[k][0] != -1)
				k++;
			n.edges[k][0] = e.dest;
			n.edges[k][1] = e.type;

			k = 0;
			while (n2.prnts[k] != -1)
				k++;
			n2.prnts[k] = e.src;
		}

		// processGraph();
		// setAppropriateSize();
		return graphName;
	} // end readBIF

	/**
	 * This method writes a graph in XMLBIF ver. 0.3 format to a file. However,
	 * if is reloaded in GraphVisualizer we would need to layout the graph again
	 * to display it correctly.
	 * 
	 * @param filename
	 *            The name of the file to write in. (will overwrite)
	 * @param graphName
	 *            The name of the graph. (will be the name of network tag in
	 *            XMLBIF)
	 * @param nodes
	 *            Vector containing all the nodes
	 * @param edges
	 *            Vector containing all the edges
	 */
	public static void writeXMLBIF03(String filename, String graphName,
			FastVector nodes, FastVector edges) {
		try {
			FileWriter outfile = new FileWriter(filename);

			StringBuffer text = new StringBuffer();

			text.append("<?xml version=\"1.0\"?>\n");
			text.append("<!-- DTD for the XMLBIF 0.3 format -->\n");
			text.append("<!DOCTYPE BIF [\n");
			text.append("	<!ELEMENT BIF ( NETWORK )*>\n");
			text.append("	      <!ATTLIST BIF VERSION CDATA #REQUIRED>\n");
			text.append("	<!ELEMENT NETWORK ( NAME, ( PROPERTY | VARIABLE | DEFI"
					+ "NITION )* )>\n");
			text.append("	<!ELEMENT NAME (#PCDATA)>\n");
			text.append("	<!ELEMENT VARIABLE ( NAME, ( OUTCOME |  PROPERTY )* )"
					+ " >\n");
			text.append("	      <!ATTLIST VARIABLE TYPE (nature|decision|utility"
					+ ") \"nature\">\n");
			text.append("	<!ELEMENT OUTCOME (#PCDATA)>\n");
			text.append("	<!ELEMENT DEFINITION ( FOR | GIVEN | TABLE | PROPERTY"
					+ " )* >\n");
			text.append("	<!ELEMENT FOR (#PCDATA)>\n");
			text.append("	<!ELEMENT GIVEN (#PCDATA)>\n");
			text.append("	<!ELEMENT TABLE (#PCDATA)>\n");
			text.append("	<!ELEMENT PROPERTY (#PCDATA)>\n");
			text.append("]>\n");
			text.append("\n");
			text.append("\n");
			text.append("<BIF VERSION=\"0.3\">\n");
			text.append("<NETWORK>\n");
			text.append("<NAME>" + XMLNormalize(graphName) + "</NAME>\n");

			// Writing all the node names and their outcomes
			// If outcome is null(ie if the graph was loaded from DOT file) then
			// simply write TRUE
			for (int nodeidx = 0; nodeidx < nodes.size(); nodeidx++) {
				GraphNode n = (GraphNode) nodes.elementAt(nodeidx);
				if (n.nodeType != GraphNode.NORMAL)
					continue;

				text.append("<VARIABLE TYPE=\"nature\">\n");
				text.append("\t<NAME>" + XMLNormalize(n.ID) + "</NAME>\n");

				if (n.outcomes != null)
					for (int outidx = 0; outidx < n.outcomes.length; outidx++)
						text.append("\t<OUTCOME>"
								+ XMLNormalize(n.outcomes[outidx])
								+ "</OUTCOME>\n");
				else
					text.append("\t<OUTCOME>true</OUTCOME>\n");

				text.append("\t<PROPERTY>position = (" + n.x + "," + n.y
						+ ")</PROPERTY>\n");
				text.append("</VARIABLE>\n");
			}

			// Writing all the nodes definitions and their probability tables
			// If probability table is null then simply write 1 for all
			// the posible outcomes of the parents
			for (int nodeidx = 0; nodeidx < nodes.size(); nodeidx++) {
				GraphNode n = (GraphNode) nodes.elementAt(nodeidx);
				if (n.nodeType != GraphNode.NORMAL)
					continue;

				text.append("<DEFINITION>\n");
				text.append("<FOR>" + XMLNormalize(n.ID) + "</FOR>\n");
				int parntOutcomes = 1;
				if (n.prnts != null)
					for (int pidx = 0; pidx < n.prnts.length; pidx++) {
						GraphNode prnt = (GraphNode) nodes
								.elementAt(n.prnts[pidx]);
						text.append("\t<GIVEN>" + XMLNormalize(prnt.ID)
								+ "</GIVEN>\n");
						if (prnt.outcomes != null)
							parntOutcomes *= prnt.outcomes.length;
					}

				text.append("<TABLE>\n");
				for (int i = 0; i < parntOutcomes; i++) {
					if (n.outcomes != null)
						for (int outidx = 0; outidx < n.outcomes.length; outidx++) {
							text.append(n.probs[i][outidx] + " ");
						}
					else
						text.append("1");
					text.append('\n');
				}
				text.append("</TABLE>\n");
				text.append("</DEFINITION>\n");
			}

			text.append("</NETWORK>\n");
			text.append("</BIF>\n");

			outfile.write(text.toString());
			outfile.close();
		} catch (IOException ex) {
			ex.printStackTrace();
		}
	} // writeXMLBIF

	/**
	 * XMLNormalize converts the five standard XML entities in a string g.e. the
	 * string V&D's is returned as V&amp;D&apos;s
	 * 
	 * @author Remco Bouckaert (rrb@xm.co.nz)
	 * @param sStr
	 *            string to normalize
	 * @return normalized string
	 */
	private static String XMLNormalize(String sStr) {
		StringBuffer sStr2 = new StringBuffer();
		for (int iStr = 0; iStr < sStr.length(); iStr++) {
			char c = sStr.charAt(iStr);
			switch (c) {
			case '&':
				sStr2.append("&amp;");
				break;
			case '\'':
				sStr2.append("&apos;");
				break;
			case '\"':
				sStr2.append("&quot;");
				break;
			case '<':
				sStr2.append("&lt;");
				break;
			case '>':
				sStr2.append("&gt;");
				break;
			default:
				sStr2.append(c);
			}
		}
		return sStr2.toString();
	} // XMLNormalize

} // BIFParser
